[Datenschleuder] [66]    AES

AES Eine schwerwiegende Entscheidung wurde von US-amerikanischen Standardinstitut NIST in die Wege geleitet. Nachdem der 1976 standardisierte DES-Algorithmus in die Jahre gekommen ist, wurde mit der Kür eines Nachfolger begonnen. Das NIST spricht zwar "nur" von einer geplanten Lebensdauer von 20-30 Jahren für den Advanced Encryption Standard (AES), die Erfahrung mit Standards hat jedoch gezeigt, daß sich wahrscheinlich noch unsere Urenkel mit AES auseinandersetzen müssen. DES ist tot Jahrelang hatten Kryptographen gewarnt, daß der bisherige Verschlüsselungsstandard DES mit seiner 56 bit Schlüssellänge durch ein komplettes Absuchen des Schlüsselraumes zu knacken ist. Während bisher lediglich auf der akademischen Ebene Bauanleitungen für Descracker existierten und jeder ernstzunehmende Sicherheitsberater auf die hohe Wahrscheinlichkeit hinwies, daß sowohl Geheimdienste, als auch gut organisierte Konzerne und Verbrecherorganisationen solche Baupläne umsetzten könnten, war am 17. Juli die Stunde der "good guys" gekommen. Während das unter anderem auf dem HIP Festival vorgestellte CCC Projekt eines DES Crackers leider in der Diskussionsphase stecken blieb, bauten die amerikanische Kollegen von der "Electronic Frontier Foundation (EFF)" für 250.000 $ eine "Höllenmaschine" (Amtsgericht Hannover), welche innerhalb von 56 Stunden DES endgültig entzauberte. Unter http://www.eff.org/descracker/ können ambitioniert Bastler auch gleich eine Bauanleitung bestellen oder direkt über http://www.replay.com/ eine von den Autoren ausdrücklich begrüßte gescannte Version downladen. Besonders dramatisch an der Geschichte ist die kryptoanalytische Einfachheit des Angriffes, da dieser nur die Bekanntheit des verschlüssleten Textes voraussetzt (known-ciphertext Angriff). Der Angreifer hört den Geheimtext ab und probiert einfach alle Schlüssel durch. Falls ein falscher Schlüssel gewählt wurde entsteht beim Entschlüsseln ein wunderschön zufälliges Rauschen. Sollte das Ergebnis sich von einer Zufallsausgabe unterscheiden ist mit hoher Wahrscheinlichkeit der richtige Schlüssel gefunden. Advanced Encryption Standard Aus diesen Gründen schrieb das US-amerikanische "National Institute of Standards and Technologie" am 12. September 1997 einen Wettbewerb für den Advanced Encryption Standard (AES) aus. Im Gegensatz zum DES Verfahren sollten diesmal die Designgrundsätzte veröffentlicht und von der Kryptogemeinde öffentlich analysiert werden können. Zudem wurden die Entwickler verpflichtet nachzuweisen, daß keinen geheimen Hintertüren vorhanden sind. Weitere Grundanforderungen waren: * Blockgröße von 128 bit * Schlüssellänge 128, 192 und 256 bit * Mindestens so schnell und so sicher wie Triple-DES Die Wahl der Blockgröße war wohl eine der schwerwiegensten Entscheidungen. Für Produkte, welche die von DES als verwendete Blockgröße von 64 bit nutzen, bedeutet dies ein unter Umständen erheblicher Umstellungsbedarf. Allerdings ist eine Blockgröße von 64bit angesichts der heutigen Rechnerleistung nicht mehr zeitgemäß (matching ciphertext Angriffe). Weswegen als Schlüssellängen neben 128 bit auch 192 und 256 bit vorgesehen sind, führte selbst auf wissenschaftlichen Konferenzen zu nicht immer ernsthaften Diskussionen. Jedenfalls sollte eine 256 bit Schlüssellänge auch den Quantencomputer der von der US Regierung gefangengehaltenen Aliens, welche möglicherweise die Komplexität eines Angriffs auf die Quadratwurzel der "herkömmlichen" Komplexität reduzieren können, widerstehen!-) Vom 20.-22. August 1998 fand im kalifornischen Ventura die erste AES Konferenz statt. Im folgenden stellen wir kurz die 15 Kandidaten, welche die Vorauswahl zur ersten AES-Konferenz überstanden haben vor. Wohl ausgeschiedene Kandiaten DEAL basiert auf einer Idee von Lars Knudsen und wurde von Richard Outerbridge als AES-Kandidat eingereicht. DEAL verwendet DES als Rundenfunktion in einem 6 rundigen Feistelnetzwerk für Schlüssellängen von 128 und 192 Bit beziehundgsweise 8 Runden für 256 Bit Schlüssel. Überraschenderweise unterlief Lars Knudsen, der als einer der führenden Experten für Keyscheduling-Verfahren, mit deren Hilfe aus dem Hauptschlüssel die einzelnen Rundenschlüssel berechnet werden, gilt, gerade hier ein schwerwiegender Fehler. Stefan Luck, der dieses Jahr schon den bisher stärksten Angriff gegen Triple-DES gefunden hatte, veröffentlichte einen Angriff welcher nur 270 gewählte Klartexte benötigt. Outerbridge hat Lucks den ausgesetzten Geldpreis für die beste Analyse bereits zugesand. Der DFC Kandidat der französischen Centre National pour la Recherche Scientifique Ecole Normale Superieure besitzt eine 8 ründige Feistelstruktur und basiert auf der sogenannten Decorrelation Technik von Serge Vaudenay. DFC ist beweisbar sicher gegen Differentielle und Lineare Kryptanalyse. Allerdings verwendet er eine sehr aufwendige 32bit Multiplikation, was seinen Einsatz auf Smartcard-Systemen erheblich erschwert. Zudem fand Dan Coppersmith zahlreiche schwache Schlüssel. Frog wurde vom "führenden Kryptografen Cost-Ricas" für die TecApro Internacional S.A. vorgestellt. Er verwendet 8 Feistelrunden und ein sehr aufwendiges Keysetup. Wagner, Ferguson, und Schneier veröffentlichten eine erfolgreiche Kryptoanalyse (Differential: 258 chosen plaintexts. Linear: 256 known plaintexts). Der 8 rundige Happy Pudding Cipher (HPC) von Richard Schroeppel dürfte trotz des schönen Namens doch nur Aussenseiterchancen besitzten. LOKI 97 ist der Kandidat von Lawrie Brown, Josef Pieprzyk und Jennifer Seberry. Loki benutzt 16 Feistelrunden und ist der Nachfolger von Loki, Loki 91. Loki wurde von Lars Knudsen gebrochen und darauf hin in Loki89 umbenannt. Auch das verbesserte Loki 91 hielt einer Analyse von Lars Knudsen nicht stand. Drei mal dürft Ihr raten welches Schicksal Loki97 ereilte. Richtig, diesmal dauerte es nur wenige Tage bis Knudsen und Rijmen ihre Analyse mit den Worten:"Loki97 is broken" schliessen konnten.(Die Differentielle Kryptanalyse benötigte 256 chosen plaintexts und die Linear Kryptanalyse 256 known plaintexts.) Telekom sorgt für Heiterkeit Gründlich blamierte sich die Deutsche Telekom AG. Ihr 6 beziehungsweise 8 ründige Feistelnetzwerk MAGENTA läßt kaum einen Anfängerfehler aus. Biham, Biryukov, Ferguson, Knudsen, Schneier und Shamir cryptoanalysiserten Magenta online während der Vorstellung (264 chosen plaintexts, 264 Steps oder 233 known plaintexts, 297 Steps). Was allerdings ein wenig ein Flächenbombardement auf ein Spatzennest erinnert. Schließlich war der Angriff gegen den unglaublich schlechten Keyschedule eine einfache Übertragung des uralten Merkle/Hellmann Angriffes auf 2-Key Triple-DES und diente daher schon als Aufgabe in einer Anfängervorlesung für Kryptographie. (http://th.informatik.uni-mannheim.de/m/lucks/vorl.html, Übungsblatt 6). Die einzelnen Schwächen (Säckeweise Schwache Schlüssel,...) aufzulisten würde den Rahmen dieses Artikels sprengen. Erst nach mehrstündigen Analyse gelang es mir überhaupt einen kryptographisch starken Baustein im Algorithmus zu finden. Als Krönung dürfte Magenta allerdings zumindest den Preis als langsamster Kandidat erhalten. Die ganze Aktion kommt einem fast so vor, als ob Andy Möller auf einmal versuchen würde, um den Schwergewichtstitel zu boxen. Kandidaten mit guten Chancen für die zweite Runde CAST 256 ist die Weiterentwicklung des bekannten CAST5 Algorithmus von Carlisle Adams und Stafford Tavares. CAST5 wurde von Entrust Technologies zur kostenlosen Verwendung freigegeben und befindet sich daher in den Programmen PGP ab Version 5.0 und PGP-Disk. CAST256 verwendet ein modifiziertes Feistelnetzwerk mit 48 Runden (12 Zyklen). Crypton ist ein 12 rundiges SP-Netzwerk der koreanischen Firma Future Systems, Inc und wurde von Chae Hoon Lim vorgestellt. Die Struktur ist von SQUARE Algorithmus beeinflusst und verwendet 8x8 S-Boxen, welche gute Widerstandseigenschaften gegen differentielle und lineare Kryptoanalyse besitzten. Das Keyscheduling soll allerdings noch modifiziert werden. Der Autor Hoon Lim publiziert seit Jahren auf den besten Krypto-Konferenzen, allerdings überwiegend im Bereiche von Digitalen Signaturverfahren. E2 ist ein 12 Runden Feistelnetzwerk von NTT - Nippon Telegraph and Telephone Corporation. E2 verwendet 8x8 S-Boxen, welche gegen die verschiedenen bekannten Angriffsmethoden gehärtet und nach einer veröffentlichten Strategie ausgewählt wurden. Bruce Schneier zählt E2 zu den vier Favoriten. RC6 ist der von Ron Rivest in Zusammenarbeit mir Robshaw, Sidney und Yin für die RSA Laboratories entwickelte Nachfolger von RC5. RC6 ist ein modifiziertes Feistelnetzwerk mit 20 Runden (10 Cycles). Die Geschwindigkeit von RC6 hängt ganz wesentlich davon ab ob der jeweilige Processor variable Rotationen schnell durchführen kann. An der Verwendung von datenabhängigen Rotationen entzündete sich allerdings Kritik. Zum einen ist die Patentlage unklar, zum anderen sind die kryptografischen Eigenschaften von derartigen Rotationen noch nicht gründlich genug analysiert. RIJNDAEL ist der Kandidat von Joan Daemen und Vincent Rijmen. Er ist faktisch die 128bit Version des bekannten Square Algorithmus. Rijndael ist ein SP-Netzwerk mit 10 , 12 bzw 16 Runden. Rijndael gehört zu den schnellsten Algorithmen im Feld. Safer+ ist wie der Namen schon sagt eine Weiterentwicklung von Safer für die Cylink Corporation. Neben dem Safer-Erfinder Massey werden auch Khachtrian und Kuregian als Co-Autoren genannt. Safer+ ist ein SP-Netzwerk mit 8 , 12 bzw 16 Runden. Die Favoriten MARS ist der offizielle IBM Kandidat. Unter den Autoren ist mit Don Coppersmith auch einer der DES Väter. MARS ist ein modifiziertes Feistelnetzwerk mit 32 Runden (16 Cycles). Es verwendet Multiplikationen und datenabhängige Rotationen. Die Konstruktionsgrundsätzte für die verwendeten S-Boxen sind mit veröffentlicht, so daß die bei DES geäußerte Sorge über geheime Hintertüren stark reduziert werden dürfte. Viele Experten sehen MARS als Favoriten. Allerdings wurden Saarien äquivalente Schlüssel entdeckt, eine kryptographisch unschöne Eigenschaft und zudem erscheint die Verwendung von Multiplikationen besonders für Smartcards als sehr aufwendig. Weiterhin ist die Verwendung von Datenabhängigen Rotationen, wie schon bei RC6 diskutiert, nicht unumstritten. Ross Anderson, Eli Biham und Lars Knudsen schicken SEPENT ins Rennen. Die Autoren zählen zu den weltbesten Kryptoanalytikern. Alle drei haben wohl bereits zahlreiche Algorithmen geknackt und eine Reihe von kryptoanalytischen Angriffsmethoden, unter anderem Bihams Differentielle Kryptoanalyse, gefunden. Serpent ist ein SP-Netzwerk mit 32 Runden. Schon nach 16 Runden ist der Algorithmus sicher gegen alle bekannten Angriffe. Der Algorithmus nutzt zur Verbesserung der Performance die von Eli Biham entwickelte Bitslicing Technik Durch die Verwendung von 4x4 S-Boxen ist der Entwurf ausgesprochen hardwarefreundlich. TWOFISH ist der Blowfish-Nachfolger von Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall und Niels Ferguson. Er verwendert Feistel 16 Runden und "borgt" eine Reihe von lange Zeit getesteten und anerkannten Bauelementen. Es kommen unter anderem Withening (DESX), Schlüsselabhängige S-Boxen (CS, Blowfish) , MDS-Matrizen (Square), Pseudo Hadamard Transformationen (Safer) und feste Rotationen zum Einsatz. Das Keyscheduling verwendet die selben Konstruktionsverfahren, wie die Rundenfunktion (Blowfish). Durch die Verwendung von relativ kleinen 8x8-S-Boxen ist der Entwurf sehr smartcardfreundlich. Twofish ist sehr schnell und flexibel an die verwendeten Resourcen anpassbar. Das Design ist ausführlich dokumentiert und bietet Sicherheit gegen alle bekannten Angriffe. Die Beschreibung des Algorithmus ist sehr schön zu lesen und vermittelt einen guten Einblick in die aktuellen Entwicklungen bei der Konstruktion von Blockchiffrierern. Twofish ist bereits in einigen Programmen optional integriert z.B. GPG (www.gnupg.org) \begin {schleichwerbung} und im pretty Open PGP kompatiblen Whiteboardsystem der Univesität Mannheim (http://www.informatik.uni-mannheim.de/~rweis/research/) \end {Schleichwerbung}. Fahrplan Die öffentliche Evaluierung der verbliebenen 15 Kandidaten erfolgt bis zum 15. April 1999. Die zweite AES-Konferenz in Rom 22.-23. März 1999. Dort werden ungefähr fünf Finalisten bestimmt. Nach einer sechs bis neunmoantigen Analyse wird aus den verbleibenden Kandidaten ein Sieger bestimmt. Tip und Ausblick Es ist ein unglaublich spannender Wettkampf entbrannt. Favoriten zu nennen ist relativ schwierig. Beginnen wir mit dem einfachen Teil und tippen welche Algorithmen ausscheiden. Zunächst werden wohl die Algorithmen mit offensichtlichen Schwächen ausgesondert, also Magenta, Loki97, DEAL, FROG und wahrscheinlich auch DFC. Von den verbleibenden tippe ich noch auf HPC und Crypton als Ausscheidekandidat. Topfavoriten auf Grund ihrer Autoren sind wohl Mars, Serpent und Twofish. Für Mars sprechen trotz zahlreicher Kritikpunkte insbesondere die 3 Buchstaben IBM. Allerdings erinnert die Konstruktion eher an einen Gemischtwarenladen, als an einen sauber konstruierten Cipher. Serpent ist so langweilig konstruiert, dass er einen hohen Sicherheitsgrad bieten muss. Pi modulo Daumen entsprechen die 32 Runden, welche jeweils den ganzen Block bearbeiten, 64 Feistelrunden. DES hat deren 16. "Nicht mal Gott wird Serpent brechen können" meinte einer weltweit führender Cryptoanalyiker. (Für Nicht-Atheisten führt diese Aussage sicherlich zu lustigen Logikspielen). Mein persönlicher Favorit ist jedoch Twofish. Twofish ist schnell und baut auf gut getesteten Basisbausteinen auf. Schlüsselabhängige S-Boxen sorgen gegen hohe Resitenz auch gegen bisher unbekannte Angriffsformen. Twofish ist frei und kostenlos einsetzbar. Und least not last gehören die Autoren definitiv zu den "good guys", so dass auch deshalb nicht mit Hintertüren zu rechnen ist. Alles wird gut! Schon jetzt kann man erfreut feststellen: Der Siegesalgorithmus wird eine weltweit einsetzbare und für lange Zeit sichere symmetrische Verschlüsslung gewähren. ruediger.weis@pi4.informatik.uni-mannheim.de URLS NIST AES-Seite: http://csrc.nist.gov/encryption/aes/aes_home.htm The Block Cipher Lounge - AES: http://www.ii.uib.no/~larsr/aes.html Candidate A E S for Analysis and Reviews: http://www.dice.ucl.ac.be/crypto/CAESAR/caesar.html (Anmerkung der Redaktion: Mittlerweile gibt es bereits die AES2-Review im Netz. Seitenweise, irgendwo. Bitte selber suchen, URL gerade nicht zur Hand. Irgendwo auf jya.)

[Datenschleuder] [66]    AES